package com.zhz.leetcode.sort;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {


    public static void main(String[] args) {
        HeapSort m = new HeapSort();
        int[] nums = {5, 6, 3, 1, 4, 2, 8, 7};
        m.heapMaxSort(nums); //使用最大堆，从小到大排序
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 使用最大堆，从小到大排序
     */
    public void heapMaxSort(int[] nums) {
        for (int i = nums.length - 1; i >= 0; i--) {
            creatHeap(nums, i+1);
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
        }
    }


    /**
     * 指定数组 firstIndex - len 之间的数据进行堆化
     */
    public void creatHeap(int[] nums, int len) {
        for (int i = len / 2 - 1; i >= 0; i--) {
            deep(nums, i, len);
        }
    }

    /**
     * 使用递归方式进行堆化 这边创建的是最大堆
     */
    public void deep(int[] nums, int currIndex, int len) {
        if (currIndex >= len) return;
        int tmpSwap = currIndex;
        int left = currIndex * 2 + 1;
        int right = currIndex * 2 + 2;
        if (left < len && nums[left] > nums[tmpSwap]) {
            tmpSwap = left;
        }
        if (right < len && nums[right] > nums[tmpSwap]) {
            tmpSwap = right;
        }

        if (tmpSwap != currIndex) {
            int tmp = nums[currIndex];
            nums[currIndex] = nums[tmpSwap];
            nums[tmpSwap] = tmp;
            deep(nums, tmp, len);
        }
    }

}
